package hihocode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//骑士游历
public class KnightWave {

	//java中1em虽然是1* 10^m,但是必须是double
	static double m = 1e2;
	
	private static final int MOD = 1000000007;
	private static final int[][] dir = {{-1, 2}, {1, 2}, {-1, -2}, {1, -2}, 
		{-2, 1}, {2, 1}, {-2, -1}, {2, -1}};

	private final int rows = 8, columns = 8;
	
	private int startX, startY;
	
	private int n;
	private long res;
	
	public static void main(String[] args) {
		KnightWave object = new KnightWave();
//		long[][] a = {{1, 2}, {3, 4}};
//		long[][] b = {{3, 5}, {6, 7}};
//		long[][] cur = object.matrixMul(a, b);
//		for(int i = 0; i < cur.length; i++){
//			for (int j = 0; j < cur[0].length; j++) {
//				System.out.print(cur[i][j] + " ");
//			}
//			System.out.println();
//		}
		object.getResMatrix();
	}
	
	public void getRes(){
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			n = scanner.nextInt();
			startX = scanner.nextInt();
			startY = scanner.nextInt();
			startX--;
			startY--;
			res = 0;
			bfs();
			System.out.println("res: " + res);
		}
		scanner.close();
	}
	
	private class Node{
		int x; int y;
		int step;
		long count = 1;
		public Node(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
	//由于n太大了，1000000000
	//超时了
	//后来搜了才知道，原来考的是矩阵快速幂
	public void bfs(){
		Node temp = new Node(startX, startY);
		Queue<Node> queue = new LinkedList<>();
		queue.add(temp);
		while(!queue.isEmpty()){
			temp = queue.poll();
			if(temp.step == n){
				res = (res + temp.count) % MOD;
				continue;
			}
			// System.out.println("x : " + temp.x + " y : " + temp.y);
			for(int i = 0; i < dir.length; i++){
				int curX = temp.x + dir[i][0];
				int curY = temp.y + dir[i][1];
				if(curX < 0 || curX >= rows || curY < 0 || curY >= columns){
					continue;
				}
				Node next = new Node(curX, curY);
				next.step = temp.step + 1;
				next.count = temp.count;
				queue.add(next);
			}
		}
	}

	//比如：(R,C)可以跳到(R+1,C+2)的位置。

	// 为了描述这种关系，可以建立一个64x64的邻接矩阵；这个邻接矩阵第一维对应8X8中的每一个点，
	// 第二维维护第一维的点可跳的位置。

	//对于这样的一个矩阵，用起始矩阵1X64乘以邻接矩阵64X64，得到的一个1X64的矩阵，
	//这个矩阵的点上值表示从起始位置走一步，到达该位置有多少种方案。
	
	//Runtime: 2022ms
	public void getResMatrix(){
		Scanner scanner = new Scanner(System.in);
		long[][] map = new long[64][64];
		//初始化每个点能够跳的点
		for(int i = 0; i < rows; i++){
			for(int j = 0; j < columns; j++){
				for(int k = 0; k < dir.length; k++){
					int curX = i + dir[k][0];
					int curY = j + dir[k][1];
					if(curX >= 0 && curX < rows && curY >= 0 && curY < columns){
						//这个其实是一个对称矩阵，我们可以只处理上三角
						int u = i * columns + j, v = curX * columns + curY;
						map[u][v] = map[v][u] = 1;
						// map[i * columns + j][curX * columns + curY] = 1;
					}
				}
			}
		}
		while(scanner.hasNext()){
			n = scanner.nextInt();
			startX = scanner.nextInt();
			startY = scanner.nextInt();
			startX--;
			startY--;
			res = 0;
			//初始所在位置
			long[][] initial = new long[1][64];
			initial[0][startX * columns + startY] = 1;
			long[][] pow = pow(map, n);
			long[][] des = matrixMul(initial, pow);
			for(int j = 0; j < des[0].length; j++){
				res = (res + des[0][j]) % MOD;
			}
			System.out.println(res);
		}
		scanner.close();
	}
	
	
	//两矩阵相乘
	public long[][] matrixMul(long[][] a, long[][] b){
		if(a == null || a.length <= 0 || b == null || b.length <= 0 || a[0].length != b.length){
			throw new IllegalArgumentException("please check the input");
		}
		long[][] res = new long[a.length][b[0].length];
		for(int i = 0; i < a.length; i++){
			for(int j = 0; j < b[0].length; j++){
				long cur = 0;
				for(int k = 0; k < a[0].length; k++){
					cur = (cur + a[i][k] * b[k][j]) % MOD; 
				}
				res[i][j] = cur; 
			}
		}
		return res;
	}

	//矩阵快速幂
	public long[][] pow(long[][] a, int n){
		if(a == null || a.length <= 0 || a[0].length != a.length){
			throw new IllegalArgumentException("please check the input");
		}
		//res要初始化为单位矩阵
		long[][] res = new long[a.length][a[0].length];
		for(int i = 0; i < a.length; i++){
			res[i][i] = 1;
		}
		while(n != 0){
			if( (n & 1) == 1){
				res = matrixMul(res, a);
			}
			a = matrixMul(a, a);
			n >>>= 1;
		}
		return res;
	}
	
}
